import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 位1的个数
 * 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中
 * 设置位
 *  的个数（也被称为汉明重量）。
 * 示例 1：
 * 输入：n = 11
 * 输出：3
 * 解释：输入的二进制串 1011 中，共有 3 个设置位。
 * 示例 2：
 * 输入：n = 128
 * 输出：1
 * 解释：输入的二进制串 10000000 中，共有 1 个设置位。
 * 示例 3：
 * 输入：n = 2147483645
 * 输出：30
 * 解释：输入的二进制串 11111111111111111111111111111101 中，共有 30 个设置位。
 */

public class demo12 {
    public int hammingWeight1(int n) {
        int ret = 0;
        while (n != 0){
            n &= n - 1;
            ret++;
        }
        return ret;
    }
    public int hammingWeight2(int n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if((n & (1 << i)) != 0)
                ret++;
        }
        return ret;
    }

    /**
     * 判定字符是否唯一
     实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
     示例 1：
     输入: s = "leetcode"
     输出: false
     示例 2：
     输入: s = "abc"
     输出: true
     */
    public boolean isUnique(String astr) {
        if (astr.length() > 26) return false;
        int bitmap = 0;
        for (int i = 0; i < astr.length(); i++) {
            int x = astr.charAt(i) - 'a';
            if(((bitmap >> x) & 1) == 1) return false;
            bitmap |=  1 << x;
        }
        return true;
    }

    /**
     * 丢失的数字
     给定一个包含 [0, n] 中 n 个数的数组 nums ，
     找出 [0, n] 这个范围内没有出现在数组中的那个数。
     示例 1：
     输入：nums = [3,0,1]
     输出：2
     解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。
     2 是丢失的数字，因为它没有出现在 nums 中。
     示例 2：
     输入：nums = [0,1]
     输出：2
     解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。
     2 是丢失的数字，因为它没有出现在 nums 中。
     示例 3：
     输入：nums = [9,6,4,2,3,5,7,0,1]
     输出：8
     解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。
     8 是丢失的数字，因为它没有出现在 nums 中。
     示例 4：
     输入：nums = [0]
     输出：1
     解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。
     1 是丢失的数字，因为它没有出现在 nums 中。
     */



    public int missingNumber1(int[] nums) {
        int ret = 0;
        for(int x : nums) ret ^= x;
        for(int i = 0;i <= nums.length;i++) ret ^= i;
        return ret;

    }
    public int missingNumber2(int[] nums) {
        int n = nums.length;
        int ret = 0;
        int sum = 0;
        for(int x : nums) sum += x;
        ret = ((0+n)*(n+1)) / 2 - sum;
        return ret;
    }
    public int missingNumber3(int[] nums) {
        Set<Integer> hash = new HashSet<>();
        int n = nums.length;
        for(int i = 0;i < n ;i++) hash.add(nums[i]);
        int ret = -1;
        for(int i = 0;i <= n;i++){
            if(!hash.contains(i)){
                ret = i;
                break;
            }
        }
        return ret;
    }
    public int missingNumber4(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i)
                return i;
        }
        return n;
    }

    /**
     * 两整数之和
     给你两个整数 a 和 b ，不使用 运算符 + 和 - 计算并返回两整数之和。
     示例 1：
     输入：a = 1, b = 2
     输出：3
     示例 2：
     输入：a = 2, b = 3
     输出：5
     */
    public int getSum(int a, int b) {
        while(b != 0){
            int x = a ^ b;
            int carry = (a&b) << 1;
            a = x;
            b = carry;
        }
        return a;
    }

    /**
     * 只出现一次的数字 II
     给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。
     请你找出并返回那个只出现了一次的元素。
     你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
     示例 1：
     输入：nums = [2,2,3,2]
     输出：3
     示例 2：
     输入：nums = [0,1,0,1,0,1,99]
     输出：99
     */
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0;i < 32;i++){
            int sum = 0;
            for(int x : nums){
                if(((x >> i) & 1) == 1){
                    sum++;
                }
            }
            sum %= 3;
            if(sum == 1) ret |= 1 << i;
        }
        return ret;
    }







}
